package suanfa;

public class reorderList {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public void reorderList(ListNode head) {
        if(head==null || head.next==null || head.next.next==null) return;
        //1.找到链表的中间节点，快慢指针
        ListNode slow=head,fast=head;
        while(fast!=null && fast.next !=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //2.头插法逆序后面部分的元素
        ListNode head2=new ListNode(0);
        ListNode cur=slow.next;
        //把两个链表分离
        slow.next=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=head2.next;
            head2.next=cur;
            cur=next;
        }

        //3.合并两个链表-双指针
        ListNode h=new ListNode(0);
        ListNode cur1=head,cur2=head2.next;
        ListNode prev=h;
        while(cur1!=null){
            prev.next=cur1;
            prev=cur1;
            cur1=cur1.next;
            if(cur2!=null){
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
    }
}
